/*
实验7-2 列出连通集
分数 25
作者 陈越
单位 浙江大学

给定一个有 n 个顶点和 m
条边的无向图，请用深度优先遍历（DFS）和广度优先遍历（BFS）分别列出其所有的连通集。假设顶点从
0 到 n−1
编号。进行搜索时，假设我们总是从编号最小的顶点出发，按编号递增的顺序访问邻接点。
输入格式:

输入第 1 行给出 2 个整数 n (0<n≤10) 和 m，分别是图的顶点数和边数。随后 m
行，每行给出一条边的两个端点。每行中的数字之间用 1 空格分隔。 输出格式:

按照"{ v1​ v2​ ... vk​ }"的格式，每行输出一个连通集。先输出 DFS
的结果，再输出 BFS 的结果。 输入样例:

8 6
0 7
0 1
2 0
4 1
2 4
3 5

输出样例:

{ 0 1 4 2 7 }
{ 3 5 }
{ 6 }
{ 0 1 2 7 4 }
{ 3 5 }
{ 6 }
*/

#include "../base/MGraph.cpp"

#include <iostream>

using namespace std;

void DFS(MGraph<int, int> &graph, int u, bool *visited, void (*visit)(int)) {
    visit(u);
    // cout << u << " ";
    visited[u] = true;
    for (int v = 0; v < graph.get_num_vertex(); v++) {
        if (graph.has_edge(u, v) && !visited[v]) {
            DFS(graph, v, visited, visit);
        }
    }
}

void BFS(MGraph<int, int> &graph, int u, bool *visited, void (*visit)(int)) {
    queue<int> q;
    q.push(u);
    visited[u] = true;
    while (!q.empty()) {
        int v = q.front();
        q.pop();
        visit(v);
        // cout << v << " ";
        for (int w = 0; w < graph.get_num_vertex(); w++) {
            if (graph.has_edge(v, w) && !visited[w]) {
                q.push(w);
                visited[w] = true;
            }
        }
    }
}

void print(int u) { cout << u << " "; }

void list_dfs(MGraph<int, int> &graph) {
    bool *visited = new bool[graph.get_num_vertex()];
    for (int i = 0; i < graph.get_num_vertex(); i++) {
        visited[i] = false;
    }

    for (int i = 0; i < graph.get_num_vertex(); i++) {
        if (!visited[i]) {
            cout << "{ ";
            DFS(graph, i, visited, print);
            cout << "}" << endl;
        }
    }
}

void list_bfs(MGraph<int, int> &graph) {
    bool *visited = new bool[graph.get_num_vertex()];
    for (int i = 0; i < graph.get_num_vertex(); i++) {
        visited[i] = false;
    }

    for (int i = 0; i < graph.get_num_vertex(); i++) {
        if (!visited[i]) {
            cout << "{ ";
            BFS(graph, i, visited, print);
            cout << "}" << endl;
        }
    }
}

int main() {
    int n, m;
    cin >> n >> m;
    MGraph<int, int> graph(n);
    graph.inputWithoutWeight(m);

    list_dfs(graph);
    list_bfs(graph);

    return 0;
}